package 二叉树;

/**
 * @ClassName : _111_二叉树的最小深度
 * @Author : 骆发茂
 * @Date: 2021/12/11 18:10
 * @Description : https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
 * 起点是root根节点，终点是最靠近根节点的那个叶子节点
 *  * BFS相对DFS的最主要区别是：BFS找到的路径一定是最短的，但代价是空间复杂度比DFS大很多
 *  * 也就是说BFS常用的场景就是让你在一幅图是找到从起点start到终点end的最近距离
 *  * 当前这个题目，使用BFS，depth每增加一步，队列中的所有节点都向前进一一步，这个逻辑保证了一旦找到一个终点，走的步数是最少的
 *  * DFS实际上是靠递归的堆栈记录走过的路径的，你要找到最短路径，肯定要把二叉树中所有树杈都探索完，然后才能对比出最短路径有多长
 *  * BFS借助队列做到一步一步齐头并进，是可以在还没遍历完整棵树的时候就找到最短距离的。
 *  * DFS是线，BFS是面；DFS是单打独斗，而BFS是集体行动
 */
public class _111_二叉树的最小深度_深度优先_迭代_图灵 {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        //min_depth,左右都可以使用，不用两个变量分别个左右子树
        /*要是都一样深，min_depth是一样的，返回都一样
        * 如果不一样深，但min_depth总是会需要去Math.min比较，min_depth永远是最小的*/
        int min_depth = Integer.MAX_VALUE;
        //左子树的最小min_depth
        //minDepth(root.left),也会继续去递归，找左右子树的情况mindepth最小深度
        if (root.left != null) {
            min_depth = Math.min(minDepth(root.left), min_depth);
        }
        //右子树的最小min_depth
        if (root.right != null) {
            min_depth = Math.min(minDepth(root.right), min_depth);
        }
        //根节点本身也是要算深度的，所以+1
        return min_depth + 1;

    }
}